همه ما با تعریف ضرب ماتریسهای مربعی آشنایی داریم. حاصلضرب ماتریسهای مربعی A و B به صورت زیر تعریف می شه:

یه عنوان مثال در حالت n = 2 داریم:

همونطور که می بینید برای محاسبه هر درایه نیاز به n عمل ضرب داریم. بنابراین برای محاسبه تمامی n2 درایه ماتریس C به n3 عمل ضرب نیاز خواهیم داشت.

قبل از ادامه بحث به مثال زیر توجه کنید:

این مثال نشون می ده که اضافه کردن سطرها و ستونهای صفر به ماتریس تاثیری در جواب نهایی حاصلضرب نداره. (البته این مطلب رو می شه به صورت منطقی و عبارات ریاضی هم اثبات کرد.)

حالا فرض کنید مقدار n توانی از عدد 2 باشه (اگه اینطور نبود با اضافه کردن تعداد مناسبی از سطرها و ستونهای صفر مرتبه ماتریسها رو به توانی از عدد 2 می رسونیم). هر کدوم از ماتریسهای A و B رو به چهار زیر ماتریس به فرم زیر تقسیم می کنیم:

به راحتی می شه ثابت کرد همواره داریم:

 ذ             

اما آیا این تقسیم بندی تاثیری در بهینه شدن تعداد محاسبات داره؟

فرض کنیم ( T ( n تعداد ضربهای لازم برای محاسبه حاصلضرب این دو ماتریس - با استفاده از زیرماتریسها - رو نشون بده. پس داریم:

با حل این رابطه بازگشتی به نتیجه زیر می رسیم:

که نشون می ده همچنان n3 عمل ضرب برای محاسبه حاصلضرب نیاز هست.

ولکر استراسن با بررسی هایی که انجام داد الگوریتمی برای ضرب ماتریسها با استفاده از تقسیم بندی ارائه داد که به جای هشت عمل ضرب در هر مرحله، هفت عمل نیاز هست. به این ترتیب داریم:

مثلا اگه n برابر 1024 باشه:

یعنی در این حالت زمان محاسبه حاصلضرب به روش استراسن نسبت به حالت عادی نزدیک به چهار برابر کمتر می شه!

و اما روش استراسن:

در این روش ماتریسهای زیر که همه از مرتبه n / 2 هستن از روی زیر ماتریسهای ماتریسهای A و B ساخته می شن:

 استراسن ثابت کرده زیرماتریسهای متناظر ماتریس حاصلضرب از رابطه های زیر به دست می یان:

همونطور که مشاهده می کنید تنها 7 عمل ضرب در هر مرحله برای محاسبه نیاز هست. تقسیم کردن ماتریسها به چهار بخش - برای محاسبه به روش استراسن - تا زمانی ادامه پیدا می کنه که مرتبه ماتریسها به 2 برسن. وقتی به این مرحله رسیدیم با تعریف اصلی ضرب ماتریسها حاصلضرب رو محاسبه می کنیم.

برنامه ضرب ماتریسها به روش استراسن رو که ماتریسها رو از فایلی گرفته و حاصلضرب رو هم در فایل دیگه ای می نویسه می تونید از اینجا دریافت کنید. توجه داشته باشید که در این برنامه از کلاس ماتریس (قبلا در سایت معرفی شده) استفاده کردیم. توابع عضو این کلاس کار محاسبه حاصلضرب به روش استراسن رو بسیار آسان می کنن.

نکات مهم:

?- علت اینکه چرا فقط عمل ضرب رو بررسی کردیم و عمل جمع رو در نظر نگرفتیم این بود که ضرب خیلی هزینه بیشتری نسبت به جمع داره.

?- این روش رو به راحتی می شه به ضرب ماتریسهای غیر مربعی تعمیم داد. تغییرات لازمه رو به عنوان تمرین به خوانندگان عزیز واگذار می کنیم.